package com.gorkr.labuladong.data_struct.array;

import org.junit.jupiter.api.Test;

/**
 * 二分查找是 log n
 * 快排 是 nlogn
 *
 * @author gorkr
 * @date 2022/07/26 12:45
 **/
public class M33SearchInRotatedSortedArray {

    // 这个方法遍历了一遍  所以是on... 傻逼
    public int search(int[] nums, int target) {
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        // 遍历找到最小值的index 就是偏移量
        int i = 0, j = 1;
        int offset = 0;
        for (; j < nums.length; j++, i++) {
            if (nums[i] > nums[j]) {
                break;
            }
        }
        offset = j == nums.length ? 0 : j;

        // 二分查找
        int low = offset, high = offset + nums.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int num = nums[mid % nums.length];
            if (num == target) {
                return mid % nums.length;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;


    }

    public int search2(int[] nums, int target) {
        int n = nums.length;
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid]==target){
                return mid;
            } else if (nums[0]<=nums[mid]) {
                // 这个mid-1 不会 月越界嘛
                // 左边有序
                if(target>=nums[0]&&target<=nums[mid]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else {
                if(target>=nums[mid]&&target<=nums[n-1]){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }

        }
        return -1;


    }


    @Test
    public void test() {
        int[] nums = {3,1};
//        int[] nums = {0,4,5,6,7};
//        int[] nums = {8, 5, 6, 7,};

        System.out.println(search2(nums, 0));
    }
}
    